package someTestExcemple.huaweiOd.doublepointer;

import java.util.Scanner;

public class GreedyMonkey_od1 {

    //豆包给的答案

    /**、
     *  整体转化思路
     * 由于猴子只能从两端取香蕉，拿 N 次后，
     * 剩下的是中间连续的 数组长度 - N 串香蕉。
     * 为了让猴子拿到最多的香蕉，就需要让剩下的中间这部分香蕉数量最少。
     * 所以，我们可以把问题转化为找出长度为
     * 数组长度 - N 的连续子数组的最小和，用数组的总和减去这个最小和，就能得到猴子能获取的最大香蕉数。
     * 思路分析
     * 本题可以使用滑动窗口的思想来解决。猴子每次只能从行的开头或者末尾获取香蕉，
     * 并且只能获取 N 次，那么我们可以枚举从左边取 i 个香蕉，
     * 同时从右边取 N - i 个香蕉的所有情况，计算每种情况下获取香蕉的总数，找出其中的最大值。
     * 具体步骤如下：
     * 读取输入的数组长度、数组元素和获取次数 N。
     * 计算数组的总和 totalSum。
     * 我们可以将问题转化为求长度为 数组长度 - N 的连续子数组的最小和 minSum。
     * 最终猴子能获取的最大香蕉数就是 totalSum - minSum。
     * 复杂度分析
     * 时间复杂度：
     * O(n)，其中
     * n是数组的长度。主要的时间开销在于计算数组总和和滑动窗口的过程，每个元素最多被访问两次。
     * 空间复杂度：
     * O(1)只使用了常数级的额外空间。
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取数组长度
        int n = scanner.nextInt();
        int[] numbers = new int[n];
        // 读取数组元素
        for (int i = 0; i < n; i++) {
            numbers[i] = scanner.nextInt(); //如果输入是以空格分隔，可以直接用nextInt()
        }
        // 读取获取次数
        int N = scanner.nextInt();
        scanner.close();

        // 计算数组的总和
        int totalSum = 0;
        for (int num : numbers) {
            totalSum += num;
        }

        // 计算长度为 n - N 的连续子数组的最小和
        int windowSize = n - N;
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }
        int minSum = windowSum;
        //滑动窗口不断求长度N-K连续子数组的最小和 --可以自己画出一个滑动窗口去理解
        for (int i = windowSize; i < n; i++) {
            windowSum = windowSum + numbers[i] - numbers[i - windowSize];
            minSum = Math.min(minSum, windowSum);
        }


        // 计算猴子能获取的最大香蕉数
        int maxBananas = totalSum - minSum;
        System.out.println(maxBananas);
    }
}
